class Solution {
public:
    int ret = 0;
    int findTargetSumWays(vector<int>& nums, int target) {
        int pathadd = 0;
        dfs(nums, target, 0, pathadd);
        return ret;
    }
    void dfs(vector<int>& nums, int target, int i, int pathadd) {
        if (i == nums.size()) {
            if (pathadd == target)
                ret++;
            return;
        }
        dfs(nums, target, i + 1, pathadd + nums[i]);
        dfs(nums, target, i + 1, pathadd - nums[i]);
    }
};
class Solution {
public:
    string path;
    vector<string> ret;
    vector<string> letterCasePermutation(string s) {
        dfs(s, 0);
        return ret;
    }
    void dfs(string s, int x)
    {
        if (path.size() == s.size())
        {
            ret.push_back(path);
            return;
        }
        for (int i = x; i < s.size(); i++)
        {
            if (s[i] <= 'z' && s[i] >= 'a')
            {
                path += s[i] + 'A' - 'a';
                dfs(s, i + 1);
                path.pop_back();
                path += s[i];
                dfs(s, i + 1);
                path.pop_back();
            }
            else if (s[i] <= 'z' && s[i] >= 'A')
            {
                path += s[i] - 'A' + 'a';
                dfs(s, i + 1);
                path.pop_back();
                path += s[i];
                dfs(s, i + 1);
                path.pop_back();
            }
            else
            {
                path += s[i];
                dfs(s, i + 1);
                path.pop_back();
            }
        }
    }
};
class Solution {
public:
    bool flag[20];
    int count = 0;
    int countArrangement(int n) {
        dfs(n, 1);
        return count;
    }
    void dfs(int size, int pos)
    {
        if (pos == size + 1)
        {
            count++;
            return;
        }
        for (int i = 1; i <= size; i++)
        {
            if (flag[i] == false && (pos % i == 0 || i % pos == 0))
            {
                flag[i] = true;
                dfs(size, pos + 1);
                flag[i] = false;
            }
        }
    }
};



















